import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-08-18
 * Time: 15:45
 */
//https://leetcode.cn/problems/substring-with-concatenation-of-all-words/submissions/654145230/
public class Test {
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list=new ArrayList();
        int size=words.length;
        int len=words[0].length();
        int n=s.length()-size*len;
        if(n<0){
            return list;
        }
        HashMap<String,Integer> map=new HashMap();
        for(int i=0;i<size;i++){
            int val=map.getOrDefault(words[i],0);
            map.put(words[i],val+1);
        }
        for(int i=0;i<len;i++){
            HashMap<String,Integer> map2=new HashMap(map);
            for(int p1=i,p2=i;p2<=s.length()-len;p2+=len){
                String str2=s.substring(p2,p2+len);
                if(map2.containsKey(str2)){
                    int val=map2.get(str2);
                    if(val==1){
                        map2.remove(str2);
                    }
                    else{
                        map2.put(str2,val-1);
                    }
                    if(map2.size()==0){
                        list.add(p1);
                        String str1=s.substring(p1,p1+len);
                        map2.put(str1,1);
                        p1+=len;
                    }
                }
                else{
                    String str1=s.substring(p1,p1+len);
                    while(!str1.equals(str2)){
                        int val=map2.getOrDefault(str1,0);
                        map2.put(str1,val+1);
                        p1+=len;
                        str1=s.substring(p1,p1+len);
                    }
                    p1+=len;
                }
            }
        }
        return list;
    }
    public static void main(String[] args) {
        String str="barfoofoobarthefoobarman";
        String[] arr={"bar","foo","the"};
        List<Integer> list=findSubstring(str,arr);
        System.out.println(list.toString());
    }
}
